Solid-modeling in the realm of computer-aided shape design has rapidly emerged as one of the most important and challenging fields of manufacturing research and development. Although activity in this area was initiated by computerized drafting systems serving as no more than electronic drafting tables, its applications today exist in areas ranging from realistic image generation to CAD/CAM and robotics.
The roots of solid-modeling technology can be traced back to the computer-aided drafting systems that were developed during the early 70's; these systems--aptly called wireframe systems--could only handle the drafting of primitive points and curves. Soon, however, the need was felt for extending this facility to not only drafting with CAD systems but designing with them. Since solid parts cannot be modeled unambiguously by only points and lines, drafting systems were soon replaced by the so called solid-modeling systems. Today there are a host of solid-modeling systems available from commercial vendors or from universities.
The use of solid-modeling systems, however, has not been able to graduate much beyond producing shaded-graphics and computing mass-properties. Even for these simple applications, the domain of the modeling system is severely restricted. Amongst the variety of reasons that can be cited for the break in the previously phenomenal growth-rate of this technology is the fact that the algorithms used for various processing needs within solid-modeling systems are either not efficient, not reliable, or not general enough in their domain of application.
The ability to compute the intersection of two surfaces usually forms the heart of a solid-modeling system. Such processing is useful not only in building an internal representation for the object from its description, but also in applications such as collision-detection, that are built upon it. Many algorithms have been proposed to compute intersections of surfaces. However, the lack of a computationally efficient algorithm applicable to a wide range of surfaces has made the application of solid modeling systems infeasible in areas such as robotics, where complex processing operations such as sweeping are required.
Reliable intersection algorithms are known for quadric surfaces but they are not applicable to other surfaces such as bicubic patches or B-spline surfaces since they capitalize heavily on properties specific to the class of quadric surfaces. On the other hand, there are edge-tracking algorithms implemented in solid-modeling systems such as BUILD, ROMULUS and TIPS-1 that are potentially applicable to a wide variety of surfaces, but they need an initial point on each component of the intersection set before they can trace it out. Since there are no known reliable methods to even determine the number of components of the intersection set in general, these algorithms tend to be unreliable. In general, each algorithm has some advantages and disadvantages; there is no clear supremacy of any one intersection algorithm over the others and research continues on almost all of them.
Algorithms designed to compute intersections of surfaces need to satisfy certain criteria that arise in the context of solid-modeling. Some of these considerations are generality, reliability, accuracy, robustness and speed. An intersection algorithm should be general enough to handle as wide a variety of surfaces as exists in the domain of a solid-modeling system. For systems that model all surfaces under a uniform scheme the criterion is met automatically by any one intersection algorithm. However, for systems that use surface-specific properties in order to design special purpose, high speed algorithms, the amount of work required to include a new surface in the modeling domain can be prohibitive. This inhibits the upward expansion of a solid-modeling system and supports, at best, a very constrained modeling environment.
The intersection for geometric entities may be invoked in a solid-modeling environment towards two different ends:
1. to detect the intersection of two solids--here only a boolean result is desired--or PA1 2. to construct a representation of the intersection set from the representations of the intersection solids.
Lack of reliability has different implications in the two above cases.
For purely detection purposes, reliability is important from the point of view of functionality. For example, in the automatic generation of numerical code for machining, a rapid traversal command may be inserted along a path where no collision with the workpiece or the fixtures is detected. However, if, in fact, there is a collision, then the tool is liable to break since tools are typically not designed to handle cutting at feed-rates of the order of rapid-traversal speeds. Similarly reliability is crucial in applications such as robot-motion-simulation and part-assembly verification systems.
When the intersection operation is used to construct a representation of the intersection set from the representation of the intersecting solids then unreliable intersections can cripple the algorithm by creating inconsistent topological data which do not permit proper termination of the algorithm. Considerable care therefore needs to be taken to detect all components of the intersection set. Algorithms suffering from this problem can be found in solid-modeling systems such as TIPS-1. The property of a solid-modeling system that prevents a system from terminating due to such internal errors, is also referred to in literature as robustness.
An intersection algorithm that computes approximate intersections from object representations does so only with a certain accuracy. The inaccuracies due to the algorithm itself are different from and in addition to those due to roundoff errors in floating point digital arithmetic. Such systems must then be able to compute how close the approximations are to the actual intersection sets. Different definitions of "closeness" may be formulated--each meaningful in the context of a desired application. One could, for example, call an intersection small if the diameter of each face is smaller than a defined .epsilon.. On the other hand it may be called negligible if two planes can be determined that are some .epsilon. apart and contain the intersection set between them.
The need to determine whether an intersection is meaningful or not exists, for example, in keeping topological information consistent and in applications such as part assembly verification. Accuracy measures are also needed in order to estimate faithfulness of representation under various operations. In a flexible modeling system, intersection sets may be further operated on by functions such as sweep, intersect, etc. The representation of the final object so created may be geometrically--and even topologically--far from its actual representation because of accumulation of inaccuracies and magnifications thereof during operations. Such magnifications occur, for example, when points near a singularity are mapped; small errors in the points can get magnified to appreciable amounts in such operations.
The desire for high speed intersection operations, although practically contradictory to the idea of reliable intersections, is almost as important. Speed is essential for an effective design and manufacturing environment based on solid-modeling. In applications such as NC machining, thousands of swept volumes are typically created--one due to each cutter move. Each one of these is treated as a solid and subtracted from the workpiece. Constructing the actual representation of the finished workpiece from such complex solids can take upwards of 2 to 3 hours on a high speed mainframe.
The existing methods for intersections of solids may broadly be classified into two categories: exact and approximate methods. This categorization is not very rigid and is based broadly on the level of approximations that the intersection algorithm may assume. It is emphasized that this distinction is fairly nebulous and a wide-variety of algorithms pass off as what is known in literature as "semi-analytical methods".
The methods that fall into the exact method category are those that derive an exact representation of the intersection set through algebraic or semi-algebraic means from exact representations of the intersecting surfaces. They incorporate techniques from algebraic geometry and numerical linear-algebra to yield algorithms that are systematic are reliable. The substitution method, quantifier elimination method, Levin's Algorithm and Ocken's Method, are examples of the exact method intersection algorithm.
In contrast with the exact methods, the number of algorithms in the category of approximate methods is much larger. Also these methods are much more widely used in current systems because they are easier to encode and often more general. However, this is almost always at the cost of reliability and accuracy. Some algorithms are based on fairly sophisticated mathematical techniques while others are purely searching schemes adapted for the intersection problem. One numerical method, known as Morgan's Method and incorporated into GMSolid, has been found successful in practice. However, the method is good only for the intersections of three surfaces that yield a finite set of points and is not meant to compute a representation of the intersection of two surfaces. It can be used to compute a set of points along an edge of intersection, but it is not clear if it does so reliably and efficiently. Moreover, the method is limited to algebraic surfaces and degrades very fast with the degree of equations involved.
Also in the class of approximate methods are the polygonal algorithms. These algorithms compute intersections of a faceted representation (a piece-wise linear approximation) of the intersection surfaces. The computations involved are simple and fast, and hence, numerous commercial geometric modeling systems (such as Geomod, CITIA etc.) based on this intersection algorithm have cropped up. A very serious disadvantage of this algorithm, however, is its lack of reliability and accuracy: approximating badly oriented surface patches as flat polygons is subject to serious pitfalls whereby erroneous results may be obtained.
Tracking algorithms are also in the approximate method category and use an iterative procedure that assumes facilities such as computations of normal vectors and computation of the distance of a point from a surface. The main idea is that given a point x on the intersection edge, a good estimate to the next one may be obtained by stepping out in the direction of the tangent vector to the edge at x. Iterative techniques can then be used to "pull" the point down to an actual intersection point.
The tracking method is very general, and has been implemented in geometric modeling systems such as TIPS-1 and ROMULUS. The disadvantage of this algorithm is again the lack of reliability: Firstly, it assumes that the intersection set is actually an edge--in reality it may be only a point or itself a surface. Secondly, it needs an initial point on each component of the intersection set to start the tracking procedure. This has to be done by some heuristic means. The method is in general inefficient as well since the number since the "pulling" operation can be very expensive.
One other algorithm belonging to the class of approximate algorithms and the one germane to the present invention is the subdivision algorithm. The subdivision algorithm for computing intersections of surfaces is based on the divide and conquer paradigm. Given a surface and a processing task, the idea is to recursively subdivide the surface into smaller and smaller patches until each patch is small enough that processing a geometric approximation to the patches instead of the patches themselves yields results accurate to within acceptable bounds. This approach was first used by Catmull (See E Catmull, "A subdivision Algorithm for Computer Display of Curved Surfaces," University of Utah Comp. Sci Dept. UTEC-CSC-74-133, 1974), in generating shaded images of curved surfaces. A very natural extension of this scheme was found in computing intersections of curved surfaces. The intersection algorithm was first developed for B-spline surfaces (See Jeffrey M. Lane and Richard R. Riesenfeld, "A Theoretical Development for the computer Generation and Display of Piecewise Polynomial Surfaces," Transactions on Pattern Analysis and Machine Intelligence, vol PAMI-2, no. 1, January 1980), and later extended to include general parametric surfaces (See S. P. Madur, P. A. Koparkar, "Interval Methods for Processing Geometric Objections", IEEE CG&A, February 1984). The subdivision algorithm is very general in terms of the surfaces it can be used for. The disclosures of the above three publications are hereby incorporated by reference herein with particular respect to computation of intersections in the Madur publication.
A big advantage of the subdivision algorithm for intersection of surfaces lies in the fact that it works with a clear interface between the intersection algorithm and representation schemes. Hence, it is not tied to any representation scheme and is limited only by the existence of the defined interface. In this respect it is similar to approximate schemes such as the tracking method for computing intersections. Another advantage of the intersection algorithm is its reliability: theoretically, since surfaces can be subdivided to as small a size as possible, all intersections can be found. However, as will be shown below the current form of the algorithm cannot be both reliable and efficient.
The subdivision algorithm is capable of computing an arbitrarily close approximation to the intersection set by subdividing the surfaces to finer and finer levels. The prescribed way of controlling the closeness of the approximation is by suitably changing the flatness criterion. It may be noted, however, that in reported versions of the algorithm, the quantitative relationship between these two measures has not been explored or exploited.
A serious drawback of the subdivision algorithm is that, since in practice infinite subdivisions are not possible and a linear approximation is used at some stage, it can sometimes miss a component of the intersection set. This becomes quite obvious if we assume that the surfaces shown in FIGS. 1 and 2 are flat to within the prescribed flatness criterion and follow the steps of the subdivision algorithm. For the case in FIG. 1, the intersection of the planar approximations to the surfaces will result in a straight line closely approximating the actual curve of intersection. For the situation in FIG. 2, however, such an approximation is not assured because the curve of intersection is a closed curve lying entirely in the interior of the surfaces. Interestingly, a curve with such a topology cannot possibly be obtained by the intersection of planar polygons.
As explained above, for some applications an intersection such as the one in FIG. 2 may be negligible. In fact, since the surfaces are flat to within some predefined tolerance limit and it may be acceptable to neglect intersections of such a nature. But for certain other applications, such an intersection may not be negligible. For example, it may be required to produce a new surface by sweeping the curve obtained by intersecting the given surfaces. In this case, it is not the flatness but the diameter of the intersection that has to be small for the intersection to be negligible. In general, a reliable solid-modeling system cannot choose to neglect such intersection.
To get around this problem, one may think of prescribing a more stringent flatness criterion. This, however, is not a general solution since--as emphasized by reported subdivision-algorithm implementations (See Elizabeth G. Houghton, Robert F. Emnett, James D. Factor, and Chaman L. Sabharwal, "Implementation of a divide-and-conquer method for the intersection of parametric surfaces", Computer Aided Geometric Design, 2, 1985, 173-183--one can constuct a case as in FIG. 2 for any given flatness criterion.
A surer remedy, motivated by the fact that computer arithmetic and real life applications work only with finite precision, is to subdivide each surface until the patches are smaller than some working precision. Another approach on similar lines would be to subdivide each surface until it is flat to within such a working precision. Once the new definition of intersection based on the working precision has been incorporated into the algorithm (mainly in the polygon-intersection procedure), it could conceivably be made to yield approximations to the intersection set that are accurate to around the working precision. However, without even going into the details of implementation of such approaches, the following objections can be raised against them. First, the initial approach will be wasteful in general since it will subdivide surfaces intersecting as in FIG. 1 to the same extent as surfaces in FIG. 2. In the latter case, some new topological information may be uncovered by the refined subdivision. However, the only result of refined subdivision for a situation as in FIG. 1 is to further improve the already good approximation of the edge of intersection. Secondly, similar objection can be raised against the second approach. The intersection for all cases will have to be computed to working precision before the topological aspects--such as the number of components of the intersection set--are known. This is clearly wasteful in an application such as collision detection where it would be sufficient to determine the existence or non-existence of any components. Thirdly, a small tolerance would cause a proliferation of surface patches. Hence intersections may be computed reliably, but only at a considerably cost in terms of storage and computations.